#-*- encoding: utf-8 -*-
from math import *

class tree(object):
    value = None # ключ
    level = 0 # уровень
    pos = 0 # позиция
    left = None # левый указатель
    right = None # правый указатель

    def __init__(self,key=None,level=0,pos=0):
        self.value = key
        self.level = level
        self.pos = pos


def findNode(node,t):
    if t==None: return None
    if t.left==None or t.right==None:
        if node.level-t.level>=0: return t # уровнь выше
    r = findNode(node,t.left)
    if r!=None: return r
    r = findNode(node,t.right)
    if r!=None: return r
    return t

def addKey(key,t):
    if t==None: return
    level,pos = getLevel(key)    
    node = tree(key,level,pos)
    
    if t.value==0 and t.left==None and t.right==None: # если отсутствуют другие элементы, то элемент включается в четное поддерево в качестве корня.        
        t.left=node
    else:
        if t.value==0: addKey(node.value,t.left) # если попытка добавить к нулевому уровню, то идем в левую подветвь
        else:
            t = findNode(node,t) # поиск в дереве элемента с которым может быть связан новый элемент
            
            elems = 2**fabs(level-t.level) # количество элементов под элементом
            last_pos = t.pos*elems # позиция последнего элемента
            first_pos = last_pos-elems+1 # позиция первого элемента
            
            while not pos in xrange(int(first_pos),int(last_pos)+1): # пока позиция нового элемента не входит в интервал позиций 
                elems *= 2 # удваиваем количество элементов в интервале
                first_pos = last_pos-elems+1  # перерасчет позиции первого элемента
                
            key1 = (2**first_pos)*(2*first_pos-1) # ключ первого элемента
            key2 = (2**first_pos)*(2*last_pos-1) # ключ последнего элемента
            xkey = (key1+key2)/2 # ключ общей вершины
            
            if t.value>node.value:
                t.right = tree(t.value,t.level,t.pos)
                t.left = node
            else:
                t.right = node
                t.left = tree(t.value,t.level,t.pos)
                
            t.value = xkey
            
# вычисление уровня и позиции элемента
def getLevel(key):
    x = 1
    z = 1
    x = log(key/z,2)
    while modf(x)[0]!=0:
        z += 1
        x = log(key/z,2)
    return int(x),(int(z)+1)/2


t = tree()
t.value = 0

addKey(24,t)
addKey(6,t)
addKey(12,t)
addKey(2,t)


def printTree(t,level=0):
    if t==None: return
    if t.left!=None: print level,". parent=",t.value," left=",t.left.value
    if t.right!=None: print level,". parent=",t.value," right=",t.right.value
    printTree(t.left,level+1)
    printTree(t.right,level+1)

printTree(t)
